In [6]:
nx.draw(G)
plt.show()
Wang Haihua
🍈 🍉🍊 🍋 🍌
网络流优化问题是基本的网络优化问题，应用非常广泛，遍及通讯、运输、电力、工程规划、任务分派、设备更新以及计算机辅助设计等领域。
流从源点流出、通过路径输送、流入到汇点，从而将目标从源点输送到汇点。流在生活中十分常见，例如交通系统中的人流、车流、物流，供水管网中的水流，金融系统中的现金流，网络中的信息流。
现实中的任何路径都有最大流量（容量）的限制，在网络中也是如此，并以边的容量（Capacity）表示，一条边的流量不能超过它的容量。
把这些现实问题抽象为网络流问题，其特征是：（1）有向图上的每条边具有容量限制；（2）从源点流出的流量，等于汇点流入的流量；（3）源点和汇点之外的所有中间节点，流出的流量等于流入的流量。
注意在网络流问题中有几组概念容易混淆：
源点/汇点，起点/终点，供应点/需求点：源点是只进不出的点，汇点是只出不进的点。源点/汇点 可以指定为问题的 起点/终点，但本质上源点/汇点是由网络结构特征决定的，而不是被指定的。供应点的供应量和需求点的需求量是固定/确定的，而源点/汇点的目标是发出/接收的流量最大，不是固定值。 容量 与 流量：容量是路径（边、弧）允许的最大流通能力，用 c(i,j) 表示；流量则是路径（边、弧）上的实际流量，用 f(i,j) 表示。
网络流优化问题最重要的指标是每条边的成本和容量限制，既要考虑成本最低（最短路径问题），又要满足容量限制（最大流问题），由此产生了网络最大流问题、最小费用流问题、最小费用最大流问题。
最大流问题（Maximun flow problem）：已知每条边的容量，研究如何充分利用网络能力，使从源点到汇点的总流量最大，也即在容量网络中求流量最大的可行流。
最小费用流问题（Minimum cost problem）：已知每条边的容量和单位流量的费用，对于给定的源点、汇点流量，研究如何分配流量和路径，使总费用最小，也即在容量费用网络中求成本最低的可行流。
最小费用最大流问题（Minimum cost maximum flow），已知每条边的容量和单位流量的费用，研究网络的流量最大的路径中，费用最小的路径。简单地说，就是满足最大流的路径可能有多条，需要从其中找到成本最低的路径。
在输油管网中，通过输油管连接生产石油的油井、储存石油的油库和转运的中间泵站。各站点之间的连接及管路的容量如下表所示
| a | b | c | d | e | f | g | h | i | j | |
|---|---|---|---|---|---|---|---|---|---|---|
| a | 0 | 6 | 8 | 3 | 0 | 3 | 0 | 0 | 0 | 0 |
| b | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 7 | 10 | 5 |
| c | 0 | 0 | 0 | 4 | 0 | 4 | 0 | 0 | 3 | 0 |
| d | 0 | 0 | 0 | 0 | 3 | 0 | 6 | 4 | 0 | 0 |
| e | 0 | 7 | 0 | 0 | 0 | 0 | 0 | 0 | 3 | 4 |
| f | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 4 | 0 | 0 |
| g | 0 | 0 | 0 | 0 | 7 | 0 | 0 | 0 | 0 | 0 |
| h | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 3 | 1 |
| i | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 3 |
| j | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
import numpy as np
import matplotlib.pyplot as plt # 导入 Matplotlib 工具包
import networkx as nx # 导入 NetworkX 工具包
import pandas as pd
import random
plt.rcParams['font.sans-serif']=['SimHei']
plt.rcParams['axes.unicode_minus']=False
C = pd.DataFrame(np.zeros((10,10)).astype('int'),index=list('abcdefghij'),columns=list('abcdefghij'))
C.loc['a','b']=6
C.loc['a','c']=8
C.loc['a','d']=3
C.loc['a','f']=3
C.loc['b','i']=10
C.loc['b','j']=5
C.loc['b','h']=7
C.loc['c','d']=4
C.loc['c','f']=4
C.loc['c','i']=3
C.loc['d','e']=3
C.loc['d','g']=6
C.loc['d','h']=4
C.loc['e','b']=7
C.loc['e','i']=3
C.loc['e','j']=4
C.loc['f','h']=4
C.loc['g','e']=7
C.loc['h','g']=1
C.loc['h','j']=1
C.loc['h','i']=3
C.loc['i','j']=3
print(C.to_markdown())
| | a | b | c | d | e | f | g | h | i | j | |:---|----:|----:|----:|----:|----:|----:|----:|----:|----:|----:| | a | 0 | 6 | 8 | 3 | 0 | 3 | 0 | 0 | 0 | 0 | | b | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 7 | 10 | 5 | | c | 0 | 0 | 0 | 4 | 0 | 4 | 0 | 0 | 3 | 0 | | d | 0 | 0 | 0 | 0 | 3 | 0 | 6 | 4 | 0 | 0 | | e | 0 | 7 | 0 | 0 | 0 | 0 | 0 | 0 | 3 | 4 | | f | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 4 | 0 | 0 | | g | 0 | 0 | 0 | 0 | 7 | 0 | 0 | 0 | 0 | 0 | | h | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 3 | 1 | | i | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 3 | | j | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
C.values
array([[ 0, 6, 8, 3, 0, 3, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0, 0, 0, 7, 10, 5],
[ 0, 0, 0, 4, 0, 4, 0, 0, 3, 0],
[ 0, 0, 0, 0, 3, 0, 6, 4, 0, 0],
[ 0, 7, 0, 0, 0, 0, 0, 0, 3, 4],
[ 0, 0, 0, 0, 0, 0, 0, 4, 0, 0],
[ 0, 0, 0, 0, 7, 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0, 0, 1, 0, 3, 1],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 3],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]])
G = nx.DiGraph()
for i in C.index:
for j in C.columns:
if C.loc[i,j]==0:
continue
else:
G.add_edge(i,j,capacity=C.loc[i,j])
nx.draw(G)
plt.show()
# 求网络最大流
# maxFlowValue = nx.maximum_flow_value(G, 's', 't') # 求网络最大流的值
# maxFlowValue, maxFlowDict = nx.maximum_flow(G, 's', 't') # 求网络最大流
from networkx.algorithms.flow import edmonds_karp # 导入 edmonds_karp 算法函数
maxFlowValue, maxFlowDict = nx.maximum_flow(G, 'a', 'j', flow_func=edmonds_karp) # 求网络最大流
# 数据格式转换
edgeCapacity = nx.get_edge_attributes(G, 'capacity')
edgeLabel = {} # 边的标签
edgeLists = [] # 最大流的边的 list
for i in maxFlowDict.keys():
for j in maxFlowDict[i].keys():
if maxFlowDict[i][j] > 0: # 网络最大流的边（流量>0）
edgeLists.append((i,j))
edgeLabel[(i, j)] =str(maxFlowDict[i][j]) # 取出每条边流量信息存入边显示值
# 输出显示
print("最大流值: ", maxFlowValue)
print("最大流的途径及流量: ", maxFlowDict) # 输出最大流的途径和各路径上的流量
print("最大流的路径：", edgeLists) # 输出最大流的途径
# 绘制有向网络图
fig, ax = plt.subplots(figsize=(8, 6))
#pos = {'a':(1,1),'b':(3,1),'c':(3,5),'d':(5,1),'e':(5,5),'f':(7,1),'g':(7,5),'h':(9,1),'i':(9,5),'j':(1,5)}
#pos = {'a':(1,1),'b':(3,1),'c':(3,5),'d':(5,1),'e':(5,5),'f':(7,1),'g':(7,5),'h':(9,1),'i':(9,5),'j':(1,5)}
pos = nx.layout.circular_layout(G)
edge_labels = nx.get_edge_attributes(G, 'capacity')
ax.set_title("Maximum flow of petroleum network with NetworkX") # 设置标题
nx.draw(G, pos, with_labels=True, node_color='c', node_size=300, font_size=10,alpha=0.2) # 绘制有向图，显示顶点标签
nx.draw_networkx_edge_labels(G, pos, edgeLabel, font_color='navy') # 显示边的标签
plt.savefig('images/opt0801.png')
plt.show()
最大流值: 13
最大流的途径及流量: {'a': {'b': 6, 'c': 4, 'd': 3, 'f': 0}, 'b': {'h': 1, 'i': 0, 'j': 5}, 'c': {'d': 1, 'f': 0, 'i': 3}, 'd': {'e': 3, 'g': 1, 'h': 0}, 'f': {'h': 0}, 'h': {'g': 0, 'i': 0, 'j': 1}, 'i': {'j': 3}, 'j': {}, 'e': {'b': 0, 'i': 0, 'j': 4}, 'g': {'e': 1}}
最大流的路径： [('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'h'), ('b', 'j'), ('c', 'd'), ('c', 'i'), ('d', 'e'), ('d', 'g'), ('h', 'j'), ('i', 'j'), ('e', 'j'), ('g', 'e')]
